package com.sheng.leetcode.year2023.month04.day26;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2023/04/26
 * <p>
 * 1031. 两个非重叠子数组的最大和<p>
 * <p>
 * 给你一个整数数组 nums 和两个整数 firstLen 和 secondLen，<p>
 * 请你找出并返回两个非重叠 子数组 中元素的最大和，长度分别为 firstLen 和 secondLen 。<p>
 * 长度为 firstLen 的子数组可以出现在长为 secondLen 的子数组之前或之后，但二者必须是不重叠的。<p>
 * 子数组是数组的一个 连续 部分。<p>
 * <p>
 * 示例 1：<p>
 * 输入：nums = [0,6,5,2,2,5,1,9,4], firstLen = 1, secondLen = 2<p>
 * 输出：20<p>
 * 解释：子数组的一种选择中，[9] 长度为 1，[6,5] 长度为 2。<p>
 * <p>
 * 示例 2：<p>
 * 输入：nums = [3,8,1,3,2,1,8,9,0], firstLen = 3, secondLen = 2<p>
 * 输出：29<p>
 * 解释：子数组的一种选择中，[3,8,1] 长度为 3，[8,9] 长度为 2。<p>
 * <p>
 * 示例 3：<p>
 * 输入：nums = [2,1,5,6,0,9,5,0,3,8], firstLen = 4, secondLen = 3<p>
 * 输出：31<p>
 * 解释：子数组的一种选择中，[5,6,0,9] 长度为 4，[0,3,8] 长度为 3。<p>
 * <p>
 * 提示：<p>
 * 1 <= firstLen, secondLen <= 1000<p>
 * 2 <= firstLen + secondLen <= 1000<p>
 * firstLen + secondLen <= nums.length <= 1000<p>
 * 0 <= nums[i] <= 1000<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/maximum-sum-of-two-non-overlapping-subarrays">1031. 两个非重叠子数组的最大和</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1031 {

    @Test
    public void test01() {
//        int[] nums = {0, 6, 5, 2, 2, 5, 1, 9, 4};
//        int firstLen = 1, secondLen = 2;
//        int[] nums = {3, 8, 1, 3, 2, 1, 8, 9, 0};
//        int firstLen = 3, secondLen = 2;
//        int[] nums = {2, 1, 5, 6, 0, 9, 5, 0, 3, 8};
//        int firstLen = 4, secondLen = 3;
        // 4795  //946
        int[] nums = {
                88, 57, 38, 99, 55, 6, 82, 75, 68, 2,
                34, 73, 4, 55, 90, 45, 72, 3, 99, 90,
                71, 76, 85, 52, 35, 51, 87, 52, 55, 81,
                99, 79, 99, 73, 72, 42, 86, 77, 15, 77,
                2, 61, 50, 47, 96, 15, 90, 84, 13, 38,
                4, 39, 91, 66, 50, 47, 58, 57, 35, 85,
                17, 7, 90, 75, 49, 53, 57, 35, 1, 35,
                80, 16, 70, 58, 86, 90, 91, 95, 0, 51,
                90, 2, 27, 59, 84, 27, 91, 47, 21, 54,
                79, 29, 84, 60, 2, 42, 12, 91, 7, 90
        };
        int firstLen = 73, secondLen = 9;
        System.out.println(new Solution().maxSumTwoNoOverlap(nums, firstLen, secondLen));
    }
}

class Solution {
    public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
        // 暴力破解：维护 4 个变量，构成两个区间，保证不重叠的情况下获取最大值
        int l1 = 0, r1 = firstLen - 1;
        int l2, r2;
        int max1, max2, max = 0;
        int length = nums.length;
        // 遍历获取最大值
        while (r1 < length) {
            // 判断区间一平移之后，前段和后段是否存在足以放下区间二的宽度
            if (length - r1 - 1 > secondLen) {
                // 区间一后方空间足够
                max1 = 0;
                for (int i = l1; i <= r1; i++) {
                    max1 += nums[i];
                }
                l2 = r1 + 1;
                r2 = r1 + secondLen;
                max2 = 0;
                for (int i = l2; i <= r2; i++) {
                    max2 += nums[i];
                }
                l2++;
                r2++;
                while (r2 < length) {
                    int maxx = 0;
                    for (int i = l2; i <= r2; i++) {
                        maxx += nums[i];
                    }
                    max2 = Math.max(max2, maxx);
                    l2++;
                    r2++;
                }
                max = Math.max(max, max1 + max2);
            }
            if (l1 >= secondLen) {
                // 区间二可以放置放置于区间一的前方
                max1 = 0;
                for (int i = l1; i <= r1; i++) {
                    max1 += nums[i];
                }
                l2 = 0;
                r2 = secondLen - 1;
                max2 = 0;
                for (int i = l2; i <= r2; i++) {
                    max2 += nums[i];
                }
                l2++;
                r2++;
                while (r2 < l1) {
                    int maxx = 0;
                    for (int i = l2; i <= r2; i++) {
                        maxx += nums[i];
                    }
                    max2 = Math.max(max2, maxx);
                    l2++;
                    r2++;
                }
                max = Math.max(max, max1 + max2);
            }
            l1++;
            r1++;
        }
        return max;
    }
}
